import numpy as np
import itertools
import random
from multiprocessing import Pool
from functools import partial

class KOpt:
    @staticmethod
    def k_opt(objfuc, assembly, k=2):
        current_order = list(assembly.keys())
        best_order = current_order[:]
        best_value = objfuc(best_order)

        indices = list(range(len(current_order)))
        for combo in itertools.combinations(indices, k):
            new_order = []
            for i, j in zip([0] + list(combo), list(combo) + [len(current_order)]):
                segment = current_order[i:j]
                segment.reverse()
                new_order.extend(segment)
            if len(new_order) != len(current_order):
                raise ValueError("New order length mismatch")
            new_value = objfuc(new_order)
            if new_value < best_value:
                best_value = new_value
                best_order = new_order

        return best_order, best_value

    @staticmethod
    def random_init_sols(Decision_variable, num_sols=10):
        cities = list(Decision_variable.keys())
        random_solutions = []
        for _ in range(num_sols):
            random_solutions.append(random.sample(cities, len(cities)))
        return random_solutions

    @staticmethod
    def optimize_solution(objfuc, Decision_mapping, solution, max_k):
        best_assembly = solution
        best_value = objfuc(solution)
        current_k = 2
        while current_k <= max_k:
            best_assembly, best_value = KOpt.k_opt(objfuc, {city: Decision_mapping[city] for city in best_assembly}, k=current_k)
            current_k += 1
        return best_assembly, best_value

    @staticmethod
    def minimize(objfuc, Decision_variable, init_guess=None, max_k=5, num_processes=4):
        if init_guess is None:
            initial_solutions = KOpt.random_init_sols(Decision_variable, num_sols=6)
        else:
            initial_solutions = [init_guess] + KOpt.random_init_sols(Decision_variable, num_sols=5)

        # 使用partial来固定额外的参数
        objfuc_partial = partial(KOpt.optimize_solution, objfuc, {city: coords for city, coords in Decision_variable.items()}, max_k=max_k)

        with Pool(num_processes) as pool:
            results = pool.map(objfuc_partial, initial_solutions)

        best_assembly, best_value = min(results, key=lambda x: x[1])
        return best_assembly, best_value

def objfunc(assembly):
    coords = [Decision_variable[city] for city in assembly]
    total_distance = 0
    for i in range(len(coords) - 1):
        total_distance += np.linalg.norm(np.array(coords[i]) - np.array(coords[i + 1]))
    total_distance += np.linalg.norm(np.array(coords[-1]) - np.array(coords[0]))  # 回到起点
    return total_distance

random.seed(42)
# 生成两个长度为26的随机数列表
List_x = [round(random.uniform(0, 30), 2) for _ in range(50)]
List_y = [round(random.uniform(0, 30), 2) for _ in range(50)]

Decision_variable = {chr(ord('A') + i): (List_x[i], List_y[i]) for i in range(50)}

if __name__ == '__main__':  # 确保只有在作为主脚本运行时才执行以下代码


    best_assembly, best_value = KOpt.minimize(objfunc, Decision_variable, max_k=3)
    print("Best Assembly Order:", best_assembly)
    print("Best Value (Total Distance):", best_value)